namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0189. 旋转数组")]
    public class No0189_Rotate : AbsBaseTestItem
    {
        /*
        给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
        示例 1:
            输入: [1,2,3,4,5,6,7] 和 k = 3
            输出: [5,6,7,1,2,3,4]
            解释:
                向右旋转 1 步: [7,1,2,3,4,5,6]
                向右旋转 2 步: [6,7,1,2,3,4,5]
                向右旋转 3 步: [5,6,7,1,2,3,4]
        示例 2:
            输入: [-1,-100,3,99] 和 k = 2
            输出: [3,99,-1,-100]
            解释:
                向右旋转 1 步: [99,-1,-100,3]
                向右旋转 2 步: [3,99,-1,-100]
        说明:
            尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
            要求使用空间复杂度为 O(1) 的 原地 算法。
        */

        public override void OnTest()
        {
            Assert.TestExe(Action,
                new int[] { 1, 2, 3, 4, 5, 6, 7 }, 3,
                new int[] { 5, 6, 7, 1, 2, 3, 4 });
            Assert.TestExe(Action,
                new int[] { -1, -100, 3, 99 }, 2,
                new int[] { 3, 99, -1, -100 });
        }

        private int[] Action(int[] nums, int k)
        {
            Rotate(nums, k);
            return nums;
        }

        public void Rotate(int[] nums, int k)
        {
            int count = 0, n = nums.Length;
            k = k % n;
            for (int start = 0; count < n; start++)
            {
                int lastIndex = start;
                int lastElement = nums[start];
                do
                {
                    int targetIndex = (lastIndex + k) % n;
                    int temp = nums[targetIndex];
                    nums[targetIndex] = lastElement;
                    lastElement = temp;
                    lastIndex = targetIndex;
                    count++;
                } while (start != lastIndex);
            }
        }
    }
}
